package prefixsum;

import java.util.Arrays;

/**
 *
 * https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/1371-mei-ge-yuan-yin-bao-han-ou-shu-ci-d-nmqp/
 * 状态压缩  + 前缀和
 * 用 五位二进制数字表示数组的前缀的 a e i o u 的奇偶次数
 * 用一个数组记录种状态出现的最早位置
 * 找到上次这种状态的下标 到 当前元素下标差即可   两个相同的下标之间一定都是偶数个    如    10000  之间    u 个数和都是奇数个   相减都是偶数个
 * 为社么  最大 0b11111 = 31  要用int[32] 来统计？？？？
 * 五位二进制  最大 0b11111 = 31     0 位置用来表示  什么也没有   需要 2 ^ 5 长度 即 32个数字 来表示   用一个长度32的数组即可
 */
public class 每个元音都出现偶数次的最长子串_1371 {
    public static int findTheLongestSubstring(String s) {
        int len = s.length();
        int pos[] = new int[32]; // 状态全0  这种状态会和中间的状态冲突 全部填充  -1
        Arrays.fill(pos, -2);
        // "leetcodeisgreat" 这种 前5个 应该长度最长5   但是  用位置相减  变成了  4 - 0 = 4 了  长度不准确
        // "eleetminicoworoep" 这种  leetminicowor  最长  13   等于  13 - 0 = 13
        // "euleetminicoworoep"                          13        14 - 1 = 13  ***** 减去的其实是前面不包含的边界  ******
        //  因为数组下标从0 开始 长度有偏差   把pos【0】 = -1 多算一位来解决
        pos[0] = -1;
        int  state = 0;
        int  maxLength = 0;
        for (int i = 0; i < len ; i++) {
            switch (s.charAt(i)) {
                case 'a' : state ^= 1; break;
                case 'e' : state ^= 1<<1; break;
                case 'i' : state ^= 1<<2; break;
                case 'o' : state ^= 1<<3; break;
                case 'u' : state ^= 1<<4; break;
            }

            //  只记录最早的位置   后面的不更新 才能保证总长度最长
            if(pos[state] != -2) {
                maxLength = Math.max(maxLength, i - pos[state]); // pos[state] 位置也要算 因此 + 1
            } else {
                pos[state] = i;
            }
        }
        return maxLength;
    }


    public static void main(String[] args) {
        System.out.println(findTheLongestSubstring("leetcodeisgreat"));
        System.out.println(findTheLongestSubstring("eleetminicoworoep"));
    }
}
